package com.cqs.leetcode.tree;

class WordDictionary {

    private class Node {
        private char val;
        private boolean isLeaf;
        private Node[] children;

        public Node(char val, boolean isLeaf, Node[] children) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.children = children;
        }
    }

    private Node root;

    /**
     * Initialize your data structure here.
     */
    public WordDictionary() {
        root = new Node((char) 0, false, null);
    }

    /**
     * Adds a word into the data structure.
     */
    public void addWord(String word) {
        if (word == null || word.length() == 0) return;
        char[] chars = word.toCharArray();
        Node parent = root;
        Node child = null;
        for (int i = 0; i < chars.length; ++i) {
            char c = chars[i];
            if (parent.children == null || parent.children[c - 'a'] == null) {
                if (parent.children == null) {
                    parent.children = new Node[26];
                }
                child = new Node(c, false, null);
                parent.children[c - 'a'] = child;
            }
            if (i == chars.length - 1) parent.children[c - 'a'].isLeaf = true;
            //更新当前根节点 继续遍历
            parent = parent.children[c - 'a'];
        }

    }

    /**
     * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
     */
    public boolean search(String word) {
        if (word == null || word.length() == 0) return false;
        word = (char) 0 + word;
        char[] chars = word.toCharArray();
        return root.children != null && search(root, chars, 0);
    }

    private boolean search(Node node, char[] letters, int index) {
        if (node == null || index >= letters.length || (letters[index] != '.' && node.val != letters[index])) return false;
        //node.val 的值判断 已经在上面语句中判断了
        if ((index == letters.length - 1)) return node.isLeaf;

        //下一个字符比较
        char c = letters[++index];
        if (c == '.') {
            if (node.children != null) {
                for (int i = 0; i < 26; i++) {
                    if (node.children[i] != null && search(node.children[i], letters, index )) {
                        return true;
                    }
                }
            }
            return false;
        } else {//普通字符
            return node.children != null && search(node.children[c - 'a'], letters, index);
        }
    }

    public static void main(String[] args) {
        WordDictionary wd = new WordDictionary();

        wd.addWord("bad");
        wd.addWord("dad");
        wd.addWord("mad");
        System.out.println(wd.search("pad"));//false
        System.out.println(wd.search("bad"));//true
        System.out.println(wd.search(".ad"));//true
        System.out.println(wd.search("b.."));//true

    }
}